home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13551 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: druid.borland.com!usenet
  2. From: pete@borland.com (Pete Becker)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: 8 Apr 1996 20:04:24 GMT
  6. Organization: Borland International
  7. Message-ID: <4kbrg8$luu@druid.borland.com>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <PdvZxMlyZE9U088yn@ime.usp.br> <4k9ggs$4ov@news1.mnsinc.com>
  9. NNTP-Posting-Host: pbecker.borland.com
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <4k9ggs$4ov@news1.mnsinc.com>, huang@mnsinc.com says...
  15. >
  16. >Rogerio Brito (rbrito@ime.usp.br) wrote:
  17. >: huang@mnsinc.com (Szu-Wen Huang) wrote:
  18. >: >Falstaff (falstaff@xs4all.nl) wrote:
  19. >: >...
  20. >: >: Hashing is slightly slower than straight table lookup and can't be
  21. >: >: used when you want to delete elements from your table.
  22. >: >...
  23. >
  24. >: >Hashing can't be used when you want to delete elements?  Please explain.
  25. >
  26. >:         I think he is refering to elimination of the item of some
  27. >:         table.   In  such  case,  you  should  change  your  hash
  28. >:         function.  But if you don't have memory problems, you can
  29. >:         simply ignore the  location  after  it  is "deleted".  Or
  30. >:         depending on the implementation, you can simply unlink it
  31. >:         from your linked list (if it is the case, of course).
  32. >
  33. >Hash tables need to have null entries so the search will know that
  34. >the item doesn't exist.  I don't see why it is difficult to find
  35. >the item to be deleted and overwrite it with the null entry.  As
  36. >you said, it'll work on linked lists, but it will work also on array
  37. >implementations.
  38.  
  39.     It depends on what you use to resolve conflicting hash values for different 
  40. elements. If you resolve conflicts by rehashing, or by moving to the next 
  41. available entry in the hash array, or any other mechanism that uses the array 
  42. itself as the storage location for the conflicting value, then you can't delete 
  43. items, cause once you do there's no way to get to the ones that used to 
  44. conflict. The first one you try will map to your now-empty location, and it'll 
  45. look like it wasn't found.
  46.     If you use a linked list at each array location to resolve conflicts then 
  47. you can delete elements.
  48.  
  49.